/*
有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。

 输入：S = "qqe"
 输出：["eqq","qeq","qqe"]

  输入：S = "ab"
 输出：["ab", "ba"]
*/

#define USED 1
#define UN_USED 0

typedef char ELEMENT;
/* 定义函数指针，用于操作哈希表 */
typedef int( * Put )( char * key , char * val , int len );
typedef int( * Get )( char * key );
typedef int( * Delete )( int key );

typedef struct Node {

    char s[ 10 ];
    UT_hash_handle hh;

} Node;

int cmp( const void * a , const void * b ) {

    return *( char * )a - *( char * )b;

}

/* 哈希表对象，包括哈希表内存位置指针，增删查函数API接口 */
typedef struct Hash {

    Node * table;
    Put put;
    Get get;
    Delete del;

} Hash;

/* 声明全局变量 */
Hash hash;
int ans_len;
char * buf , **ans ;

/**
 * 根据 key 查找哈希表的值
 * @param char * key :
 * Return int : 0 , 不存在 ; 1 , 存在
 */
int get( char * key ) {

    Node * tmp = NULL;

    HASH_FIND_STR( hash.table , key , tmp );

    if( tmp == NULL ) {

        return UN_USED;

    }

    return USED;

}

/**
 * 根据 key 添加哈希表的值 val
 * @param char * key :
 * @param char * val : 
 * Return int : 0 , 不存在 ; 1 , 存在
 */
int put( char * key , char * val , int len ) {

    Node * tmp = NULL;

    HASH_FIND_STR( hash.table , key , tmp );

    if( tmp == NULL ) {

        tmp = ( Node * )malloc( sizeof( Node ) * 1 );

        strcpy( tmp -> s , key );
        HASH_ADD_STR( hash.table , s , tmp );

    } 

    return USED;

}

void backtrack( char * s , int n , int index ) {

    /* 结束条件，添加路径到结果数组中 */
    if( index == n ) {
        
        if( hash.get( buf ) == UN_USED ) {

            ans[ ans_len ] = ( char * )malloc( sizeof( char ) * ( n + 1 ) );
            strcpy( ans[ ans_len++ ] , buf );
            hash.put( buf , buf ,  n + 1 );

        }
        
        return ;

    }

    /* 遍历可操作列表，做选择 */
    for( int i = 0 ; i < n ; i++ ) {

        /* 做选择 */
        if( s[ i ] == '-' ) {

            continue;

        }

        /* 做选择 */
        buf[ index ] = s[ i ];
        char ch = s[ i ];
        s[ i ] = '-';
        backtrack( s , n , index + 1 );
        /* 撤销选择 */
        s[ i ] = ch;

    }

}

/**
 * 计算 k 个数全排列后总的情况数量
 * @param int k : the number of element in nums
 * Return int : the total number of all sort
 */
int all_sort( int k ) {

    if( k == 1 ) {

        return 1;

    }

    return all_sort( k - 1 ) * k;

}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char ** permutation( char * S , int * returnSize ) {

    int n = strlen( S );
    int max_len = all_sort( n );

    qsort( S , n , sizeof( S[ 0 ] ) , cmp );

    hash.table = NULL;
    buf = ( char * )malloc( sizeof( char ) * ( n + 1 ) );
    ans = ( char ** )malloc( sizeof( char * ) * max_len );


	/* 初始化哈希表对象 */
    hash.get = get;
    hash.put = put;
    ans_len = 0;
    buf[ n ] = '\0';

    backtrack( S , n , 0 ); 

    *returnSize = ans_len;
    return ans;

}

//-------------------------------------------------
//  方法2

char **g_res;
int    g_resSize;
char  *g_path;
int    g_pathSize;
int   *g_used;

#define SIZE 1000
#define LEN  10
int Cmp(const void *a, const void *b)
{
    return *(char*)a - *(char*)b;
}

void Backtrack(char *s, int sSize)
{
    
    if (g_pathSize == sSize) {
        char *tmp = (char*)malloc(sizeof(char) * LEN);
        memset(tmp, 0, sizeof(char) * LEN);
        memcpy(tmp, g_path, sizeof(char) * LEN);
        g_res[g_resSize++] = tmp;
        return;
    }
    
    for (int i = 0; i < sSize; i++) {
        
        if (i > 0 && s[i] == s[i - 1] && g_used[i - 1] == false) {
            continue;
        }

        if (g_used[i] == false) {
            g_used[i] = true;
            g_path[g_pathSize++] = s[i];
            Backtrack(s, sSize);
            g_pathSize--;
            g_used[i] = false;
        }
    }
}

char** permutation(char* S, int* returnSize){
    int sSize = strlen(S);

    g_res = (char**)malloc(sizeof(char*) * SIZE);
    memset(g_res, 0, sizeof(char*) * SIZE);

    g_path = (char*)malloc(sizeof(char) * SIZE);
    memset(g_path, 0, sizeof(char) * SIZE);

    g_used = (int*)malloc(sizeof(int) * SIZE);
    memset(g_used, 0, sizeof(int) * SIZE);

    g_resSize = g_pathSize = 0;
    qsort(S, sSize, sizeof(S[0]), Cmp);
    Backtrack(S, sSize);

    *returnSize = g_resSize;

    return g_res;
}


